Search Results

  1. T. Tirronen, Optimizing the Degree Distribution of LT Codes, Master's thesis, Networking Laboratory, Helsinki University of Technology, 2006 (pdf)(bib)
    Abstract: This thesis examines the problem of data transfer from the perspective of error correction codes. Recently, many new interesting transmission schemes employing erasure forward error correction have been proposed. This thesis focuses on codes approximating the ``digital fountain'', an analogy envisaging digital data as a fountain spraying drops of water, which can be collected by holding a bucket under it. The bucket eventually becomes full, regardless of the amount of water drops missing the bucket. In data transmission, the digital fountain functions in a similar fashion: packets are sent into network, and the recipient needs only a certain number of these packets to decode the original information. In practice, with good codes, this number is only slightly more than the amount of packets corresponding to the original file size. Traditional Reed-Solomon codes can be used to approximate the digital fountain, but more efficient codes also exist. LT codes are efficient and asymptotically optimal codes, especially for a large number of source blocks. LDPC codes are also presented as an alternative for approximating the digital fountain. Efficient utilization of LT codes requires carefully designed degree distributions. This work describes the distributions proposed earlier, and presents a new optimization method for generating good distributions. An iterative algorithm based on this method is also proposed. The optimization method is based on estimation of the average number of packets needed for decoding. The importance sampling approach is used to generate this estimate by simulating the LT process. After this, standard nonlinear optimization methods are employed to optimize this estimate. Numerical test results are provided to validate the correct function of the algorithm. Finally, this thesis also includes a discussion of possible applications for erasure correcting codes approximating the digital fountain, with special attention to salient implementation issues.